package 力扣.排序.堆排序;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int[] ints = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        HeapSort heapSort = new HeapSort();

        //构造大根堆
        for (int i = 1; i < ints.length; i++) {
            heapSort.nodeUp(i , ints);
        }
        //交换头节点
        for (int i = ints.length - 1; i > 0; i--) {
           heapSort.swap(ints, 0, i);
           heapSort.nodeDown(0, ints , i);
        }
        System.out.println(Arrays.toString(ints));

    }

    void nodeUp(int index , int[] ints){//上浮
        int te = ints[index];
        for (int i = (index - 1) >> 1; i >= 0; i = (i - 1) >> 1/*父节点*/) {
            int t = ints[i];
            if (t < te){
                ints[index] = t;
                index = i;
            }else{
                break;
            }
        }
        ints[index] = te;
    }
    void nodeDown(int index , int[] ints ,int end){
        int te = ints[index];
        for (int i = (index << 1) + 1; i < end; i = (i << 1)+1) {
            if (i+1 < end && ints[i] < ints[i + 1]){
                i++;
            }
            if (ints[i] > te){
                ints[index] = ints[i];
                index = i;
            }else{
                break;
            }
        }
        ints[index] = te;
    }
    void swap(int[] ints ,int i ,int j){
        int t = ints[i];
        ints[i] = ints[j];
        ints[j] = t;
    }
}
